package LeetCode.top100;

public class LC45 {
    public static void main(String[] args) {
        LC45 l = new LC45();
        int[] arr = new int[]{2,3,1,1,4};
        int jump = l.jump(arr);
        System.out.println(jump);
    }
    public int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int res = 1;
        for(int i = 0; i <= nums.length;){
            int max = -1, index = -1, cur = nums[i];
            while(cur > 0){
                if(i + cur >= nums.length - 1){
                    return res;
                } else if(i + cur + nums[i + cur] > max){
                    max = i + cur + nums[i + cur];
                    index = i + cur;
                }
                cur--;
            }
            i = index;
            res++;
        }
        return res;
    }
}
